package cn.chen.算法.十算法;

// 分治算法解决汉诺塔问题

/**
 *
 * 汉诺塔问题：
 * 将A柱子上的所有盘移动到C柱子上去。
 *
 * 其实汉诺塔只有两种情况：
 * 1、只有一个盘，直接从A-C
 * 2、有两个盘或者多个盘，多个盘直接看成是两个盘。
 *
 * 两个盘的步骤：
 * 1、A-C
 * 2、A-B
 * 3、B-C
 *
 * 所以解决汉诺塔就是递归两个盘的步骤和一个盘的步骤。
 */
public class DivideAndConquerAlgorithm {

    public static void main(String[] args){

        hanoiTower(6 ,'A','B','C');
    }

    /**
     * @param num   盘的数量
     * @param a     柱子的符号，开始移动的柱子
     * @param b     移动过程中用到的柱子
     * @param c     要移动到的柱子
     */
    public static void hanoiTower(int num,char a,char b,char c){

        // 如果只有一个盘，直接从A-C
        if(num==1) {
            System.out.println("第1个盘从"+a+"-->"+c);
            return;
        }

        // 有2个以上的盘：看成只有两个盘，上面的所有盘，下面的一个盘
        // 1、将上面的所有盘从A->B 移动过程会借助C
        hanoiTower(num-1,a,c,b);    // 从a->b  ,借助c

        // 2、将最下面的一个盘从A->C
        System.out.println("第"+num+"个盘从"+a+"-->"+c);

        // 3、将B柱子上的所有盘移动到C盘  移动过程中借助A
        hanoiTower(num-1,b,a,c);
    }
}
